이중 우선 순위 큐

📔 문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

📓 제약 조건

operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
operations의 원소는 큐가 수행할 연산을 나타냅니다.
원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

📓 입출력의 예

❗1 번째

나는 일단 자바스크립트로 힙을 구현하는 방법을 잘 모르겠다.
그렇기때문에 정렬로 이 문제를 풀어 볼수있을거같아서 한번 풀어보았다 첫번째로
이중우선순위큐 역할을 해줄 클래스를 생성하고 삽입 , 최대값삭제 , 최소값삭제 , 비어있는지 체크 , 결과 불러오기 메서드를 생성한다.
처음엔 삽입을 삽입후 매번 정렬하여 $O(n)$의 방식을 사용했었는데 그것보다는 이진 탐색을 통해 삽입하는게 효과적일것이라 판단해 수정하였다.
그후 배열에 명령어와 -1 , 1을 가른다음 명령어에서 I 면 삽입을 실행하고, D면 비어있는지 체크후 최대값과 최소값을 뺄수있도록하였다.
그 후 front와 rear 포인터를 이용해 비어있으면 0,0 을 반환하고 비어있지않다면 최소값과 최대값을 리턴하는 식으로 코드를 짜보았다.

✅ 실행 코드

class 이중우선순위큐 {
  constructor() {
    this.items = [];
    this.front = 0;
    this.rear = 0;
  }

  insert(num) {
    let left = this.front;
    let right = this.rear;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (this.items[mid] < num) left = mid + 1;
      else right = mid;
    }

    this.items.splice(left, 0, num);
    this.rear++;
  }

  deleteMax() {
    this.rear--;
  }

  deleteMin() {
    this.front++;
  }

  isEmpty() {
    return this.front === this.rear;
  }

  getResult() {
    if (this.isEmpty()) return [0, 0];
    return [this.items[this.rear - 1], this.items[this.front]];
  }
}

function solution(operations) {
  const q = new 이중우선순위큐();

  for (const op of operations) {
    const [명령어, 최대최소] = op.split(" ");

    if (명령어 === "I") q.insert(Number(최대최소));
    else if (명령어 === "D") {
      if (q.isEmpty()) {
        continue;
      } else {
        if (최대최소 === "1") q.deleteMax();
        else if (최대최소 === "-1") q.deleteMin();
      }
    }
  }

  return q.getResult();
}

📚 문제 느낀점

힙을 사용하여 풀지 않고 정렬로 풀어서 비겁하게 푼거같긴하다.
그래도 이 방법상 삽입은 오래걸려도 최대값과 최소값 부분에서 속도가 많이 빠를것이다.

© 문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/42628